1245D - Shichikuji and Power Grid - CodeForces Solution

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mx=4e6+10;
 
struct node{
   int x,y;
   ll w;
}s[mx];
 
vector<int>e[mx];
int f[mx],a[mx],b[mx],k[mx],vis[mx];
int n,tot,c,cnt;
ll ans;
 
void init(){
	ans=cnt=0;
	tot=1;
	memset(vis,0,sizeof(vis));
	for(int i=0;i<=n;i++)
	f[i]=i;
}
 
int find(int x)
{
	return x==f[x]?f[x]:f[x]=find(f[x]); 
}
 
bool cmp(node a,node b)
{
	return a.w<b.w;
}
 
int main(){
	scanf("%d",&n);
	init();
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i],&b[i]);
	for(int i=1;i<=n;i++)
	{
	  scanf("%d",&c);
	  s[tot].x=0;
	  s[tot].y=i;
	  s[tot].w=c;
	  tot++;
        }
        for(int i=1;i<=n;i++)
	  scanf("%d",&k[i]);
	for(int i=1;i<=n;i++)
	{
	   for(int j=i+1;j<=n;j++)
	   {
	     s[tot].x=i;
	     s[tot].y=j;
	     s[tot].w=1ll*(abs(a[i]-a[j])+abs(b[i]-b[j]))*(k[i]+k[j]);
	     tot++;
	   }
        }
	sort(s+1,s+tot,cmp);
	for(int i=1;i<tot;i++)
	{
		int fx=find(s[i].x),fy=find(s[i].y);
		if(fx!=fy)
		{
		   if(s[i].x==0)
		   {
		     vis[s[i].y]=1;
	              cnt++;
	           }
	           else
	           e[s[i].x].push_back(s[i].y);
	           ans+=s[i].w;
	           f[fy]=fx;
	        }
	}
	printf("%I64d\n",ans);
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++) if(vis[i]) printf("%d ",i);
	printf("\n");
	printf("%d\n",n-cnt);
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<e[i].size();j++)
		printf("%d %d\n",i,e[i][j]);
	}
	return 0;
}